// 给你一个字符串 s，找到 s 中最长的回文子串。

// 看了题解
// 执行用时：
// 312 ms
// , 在所有 C++ 提交中击败了
// 48.36%
// 的用户
// 内存消耗：
// 378.2 MB
// , 在所有 C++ 提交中击败了
// 5.14%
// 的用户


#include<bits/stdc++.h>
#include<string>
#include<vector>
using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.size();
        vector<vector<int>> dp(len,vector<int>(len));
        int start = 0;//回文串起始位置
        int max = 1;//最大回文串大小
        // 初始化数组
        for(int i=0;i<len;i++){
            dp[i][i] = 1;
            if(i<len-1 &&s[i] == s[i+1]){
                dp[i][i+1] = 1;
                start = i;
                max = 2;
            }
        }
        for(int l=3;l<=len;l++){//回文串寻找，从3-len
            for(int i=0;i<=len-l;i++){
                int j=l+i-1;//终止字符位置
                if(s[i]==s[j] && dp[i+1][j-1]==1){
                    dp[i][j]=1;
                    start = i;
                    max = l;
                }
            }
        }
        return s.substr(start,max);
    }
};